
/********************************************************************************
Function : shortest_path
Description: Computes the shortest path between the nodes in a given NxN matrix
			 using Floyd-Warshall algorithm 
**********************************************************************************/
#include <stdio.h>

int main(){

int no_nodes=4;
int u,v;     // local variables to access the row(U) and column(V) in edge_w matrix
int k;
int R[100][100][100];
int edge_w[no_nodes+1][no_nodes+1];

//initialise the weights
for(u=1;u<=no_nodes;u++) {
	for (v=1;v<=no_nodes;v++) {
		edge_w[u][v]= 9999;      // R1=w(U,V)
	}
}
// set the appropriate weights

edge_w[1][3]=7;
edge_w[2][1]=-1;
edge_w[3][2]=6;
edge_w[3][4]=6;
edge_w[4][2]=14;
/*
edge_w[1][2]=-3;
edge_w[2][3]=1;
edge_w[2][4]=2;
edge_w[3][4]=2;
edge_w[4][1]=1;
*/
//Floys-warshall algorithm

for(u=1;u<=no_nodes;u++) {
	for (v=1;v<=no_nodes;v++) {
		R[1][u][v]= edge_w[u][v];      // R1=w(U,V)
	}
}
 
for (k=1;k<=no_nodes;k++) {
	for(u=1;u<=no_nodes;u++) {
		for (v=1;v<=no_nodes;v++) {
			R[k+1][u][v]= R[k][u][v]; 
			if( R[k+1][u][v]> R[k][u][k] + R[k][k][v])
				R[k+1][u][v]= R[k][u][k] + R[k][k][v];
		}
	}
}

for(k=1;k<=no_nodes;k++) {
	for(u=1;u<=no_nodes;u++) {
		if ( R[k][u][u]< 0)
			printf("FALSE");
	}
}

//print out the final sp matrix

for (k=1;k<=no_nodes+1;k++) {
printf("\n\n\nR(%d)\n",k);
for(u=1;u<=no_nodes;u++) {
	for (v=1;v<=no_nodes;v++) {
		printf("%d\t",R[k][u][v]);     // R1=w(U,V)
	}
	printf("\n");
	
}

}



return 0;
}
	